import com.sun.source.tree.Tree;

import java.util.*;

public class BinaryTree {
    class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    //前序遍历
    public void preOrder(TreeNode root){
        if(root == null) return ;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //前序遍历（非递归）
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                System.out.print(cur.val + " ");
                list.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list;
    }

    //中序遍历
    public void inOrder(TreeNode root){
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //中序遍历（非递归）
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);
            System.out.print(top.val + " ");
            cur = top.right;
        }
        return list;
    }


    //后序遍历
    public void postOrder(TreeNode root){
        if(root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    //后序遍历(非递归)
    public List<Character> postderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if(root == null){
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == prev){
                top = stack.pop();
                list.add(top.val);
                System.out.print(top.val + " ");
                prev = top;
            }else{
                cur = top.right;
            }
        }
        return list;
    }

//    //中后序构建二叉树
//    int postIndex = 0;
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        postIndex = postorder.length - 1;
//        return buildTreeChild(inorder,postorder,0,inorder.length - 1);
//    }
//    public TreeNode buildTreeChild(int[] inorder, int[] postorder,int inBegin,int inEnd) {
//        if(inBegin > inEnd){
//            return null;
//        }
//        TreeNode root = new TreeNode(postorder[postIndex]);
//        int rootVal = findVal(inorder,inBegin,inEnd,postorder[postIndex]);
//        postIndex--;
//        root.right = buildTreeChild(inorder,postorder,rootVal + 1,inEnd);
//        root.left = buildTreeChild(inorder,postorder,inBegin,rootVal - 1);
//        return root;
//    }
//
//    public int findVal(int[] inorder,int inBegin,int inEnd,int key){
//        for(int i = inBegin; i <= inEnd ; i++){
//            if(inorder[i] == key){
//                return i;
//            }
//        }
//        return -1;
//    }
//
//
//    //前中序构建二叉树
//    public int preIndex = 0;
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        return buildTreeChild(preorder,inorder,0,inorder.length - 1);
//    }
//    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inBegin,int inEnd) {
//        if(inBegin > inEnd){
//            return null;
//        }
//        TreeNode root = new TreeNode(preorder[preIndex]);
//        int rootIndex = findVal(inorder,inBegin,inEnd,preorder[preIndex]);
//        preIndex++;
//        root.left = buildTreeChild(preorder,inorder,inBegin,rootIndex - 1);
//        root.right = buildTreeChild(preorder,inorder,rootIndex + 1,inEnd);
//        return root;
//    }
//
//    public int findVal(int[] inorder,int inBegin,int inEnd,int key){
//        for(int i = inBegin; i <= inEnd; i++){
//            if(inorder[i] == key){
//                return i;
//            }
//        }
//        return -1;
//    }


    //二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stackp = new Stack<>();
        Stack<TreeNode> stackq = new Stack<>();
        getPath(root,p,stackp);
        getPath(root,q,stackq);
        int lenp = stackp.size();
        int lenq = stackq.size();
        if(lenp < lenq){
            int len = lenq - lenp;
            while(len != 0){
                stackq.pop();
                len--;
            }
        }else{
            int len = lenp - lenq;
            while(len != 0){
                stackp.pop();
                len--;
            }
        }
        while(!stackp.isEmpty() && !stackq.isEmpty()){
            TreeNode valp = stackp.pop();
            TreeNode valq = stackq.pop();
            if(valp == valq){
                return valp;
            }
        }
        return null;
    }

    public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
        if(root == null) return false;
        stack.push(root);
        if(root == node){
            return true;
        }
        boolean flg = getPath(root.left,node,stack);
        if(flg){
            return true;
        }
        flg = getPath(root.right,node,stack);
        if(flg){
            return true;
        }
        stack.pop();
        return false;
    }

    //二叉树的层序遍历
    public List<List<Character>> levelOrder(TreeNode root) {
        List<List<Character>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
            List<Character> tmp = new LinkedList<>();
            int size = qu.size();
            while(size != 0){
                TreeNode cur = qu.poll();
                size--;
                tmp.add(cur.val);.
                if(cur.left != null){
                    qu.offer(cur.left);
                }
                if(cur.right != null){
                    qu.offer(cur.right);
                }
            }
            ret.add(tmp);
        }
        return ret;
    }

    //根据二叉树创建字符
    public String tree2str(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        tree2strChild(root,stringBuilder);
        return stringBuilder.toString();
    }

    public void tree2strChild(TreeNode root,StringBuilder stringBuilder){
        if(root == null) return ;
        stringBuilder.append(root.val);
        if(root.left != null){
            stringBuilder.append("(");
            tree2strChild(root.left,stringBuilder);
            stringBuilder.append(")");
        }else{
            if(root.right == null){
                return;
            }else{
                stringBuilder.append("()");
            }

        }
        if(root.right != null){
            stringBuilder.append("(");
            tree2strChild(root.right,stringBuilder);
            stringBuilder.append(")");
        }else{
            return ;
        }
    }

}
